Problem 501 Find Mode in Binary Search Tree
该题就是查找在树中出现次数最多的值
主要思路:
本题主要需要利用该二叉树为二叉查找树的特性,利用中序遍历就能将所有值按照升序进行排序,所以可以转化成在一个升序排序的数组中查找出现次数最多的值.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private List<Integer> list;
private int pre;
private int cnt;
private int max;
public int[] findMode(TreeNode root) {
if(root==null){
return new int[0];
}
list=new LinkedList<>();
inOrder(root);
int[] res=new int[list.size()];
for(int i=0,size=list.size();i<size;i++){
res[i]=list.get(i);
}
return res;
}
private void inOrder(TreeNode root){
if(root==null){
return;
}
inOrder(root.left);
if(pre==root.val){
cnt++;
}
else{
cnt=1;
pre=root.val;
}
if(cnt==max){
list.add(root.val);
}
else if(cnt>max){
list.clear();
list.add(root.val);
max=cnt;
}
inOrder(root.right);
}
}
⭐Problem 504 Base 7
该问题就是进制转换
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
final static char[] digits = {
'0' , '1' , '2' , '3' , '4' , '5' ,
'6' , '7' , '8' , '9'
};
public String convertToBase7(int num) {
char buf[] = new char[33];
boolean negative = (num < 0);
int charPos = 32;
if (!negative) {
num = -num;
}
while (num <= -7) {
buf[charPos--] = digits[-(num % 7)];
num = num / 7;
}
buf[charPos] = digits[-num];
if (negative) {
buf[--charPos] = '-';
}
return new String(buf, charPos, (33 - charPos));
}
}
代码说明:
上述代码来源于Java库中有关进制转换的实现.首先定义了一个digit用于存储0-9的字符,然后将正数化为负数,这是方便正负值都能统一处理.之后就是从最后一位开始与进制取模,转化为digit中的字符,num=num/7之后num相当于进位了,依次循环,完成每位的填充.
Problem 507 Perfect Number
寻找完美数,完美数就是该数能够通过它的因子相加组成.
主要思路:
该题是一个数学问题,满足完美数的条件包含:
- 数字=13+33+53+73+…+奇数3
- 数字%9==1
上述条件后该题就比较简单了
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public static boolean checkPerfectNumber(int num) {
if (num < 5)
return false;
if (num == 6)
return true;
int sum = 0;
for (int i = 1; i < Math.sqrt(num); i+=2) {
sum = (int) (sum + Math.pow(i, 3));
if (sum == num && sum % 9 == 1)
return true;
if (sum > num)
return false;
}
return false;
}
}
Problem 532 K-diff Pairs in an Array
给定一个值,找出所有差值与该值相同的数字对,(i,j)和(j,i)为相同数字对,不重复计算
主要思路:
我采用的是最简单的思想,首先对数组进行排序,之后就是双循环找满足条件的数字对.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public int findPairs(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
Arrays.sort(nums);
for (int i=0;i<nums.length;i++){
for (int j=i+1;j<nums.length;j++)
if ((nums[j]-nums[i])==k)
set.add(nums[i]);
}
return set.size();
}
}
Problem 538 Convert BST to Greater Tree
该题要求改变二叉搜索树的结点,改变的原则是该结点加上比它大的所有结点的值.
主要思路:
我采用了队列对通过中序遍历的结点进行存储,由于树本身是二叉搜索树,所以经过中序遍历后的队列为升序排列过的队列,之后我又准备一个sum队列,该队列存储的是每个结点应该需要加上的值的大小.完成准备时候就只需要对树进行中序遍历即可,每访问到一个结点就让结点值加上sum值,之后让sum头元素出队.依次循环,完成数值更新.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int round = 0;
public TreeNode convertBST(TreeNode root) {
if (round==0){
getSum(getQueue(root));
round++;
}
if (root==null)
return null;
else {
convertBST(root.left);
root.val+=sumQueue.peek();
sumQueue.poll();
convertBST(root.right);
}
return root;
}
Queue<TreeNode> queue = new LinkedList<>();
public Queue<TreeNode> getQueue(TreeNode root){
if (root!=null){
getQueue(root.left);
queue.offer(root);
getQueue(root.right);
}
return queue;
}
Queue<Integer> sumQueue = new LinkedList<>();
public Queue<Integer> getSum(Queue<TreeNode> queue){
int sum = 0;
while (!queue.isEmpty()){
queue.poll();
for (TreeNode treeNode : queue) {
sum += treeNode.val;
}
sumQueue.offer(sum);
sum = 0;
}
return sumQueue;
}
}
Problem 543 Diameter of Binary Tree
该题要求求出树中任意两个结点的最长距离
主要思路:
首先只是考虑了左右子树之和,但是后来发现由于没说必须要经过根结点,所以其实每个点都可以是根结点,也就是说通过常规的遍历就能找到最大值.
代码实现:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
int left = 0;
int right = 0;
if (root==null)
return 0;
else {
if (root.left!=null)
left = height(root.left);
else
left = 0;
if (root.right!=null)
right = height(root.right);
else
right = 0;
if(left+right>max){
max = left+right;
}
}
diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);
return max;
}
public int height(TreeNode root){
if (root==null)
return 0;
else {
return 1+Math.max(height(root.left),height(root.right));
}
}
}